import java.util.*;

/*
题目描述：“之”字形打印二叉树
方法：设置一个标志 flag 用于记录打印方向
使用双端队列控制输出方向
 */
public class E32_2 {
    public static void main(String[] args) {
        TreeNode1 root = new TreeNode1(1);
        root.left = new TreeNode1(2);
        root.right = new TreeNode1(3);
        root.left.left = new TreeNode1(4);
        root.left.right = new TreeNode1(5);
        root.right.left = new TreeNode1(6);
        root.right.right = new TreeNode1(7);

        ArrayList<ArrayList<Integer>> res = Print(root);

        System.out.println(res);
    }

    public static ArrayList<ArrayList<Integer>> Print(TreeNode1 pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null){
            return res;
        }
        Deque<TreeNode1> deque = new ArrayDeque<>();
        boolean flag = true;
        deque.addFirst(pRoot);
        while(!deque.isEmpty()){
            int len = deque.size();
            ArrayList<Integer> temp = new ArrayList<>();
            if(flag == false){//反向
                for(int i = 0; i < len; i++){
                    TreeNode1 cur = deque.removeLast();
                    temp.add(cur.val);
                    if(cur.right != null){
                        deque.addFirst(cur.right);
                    }
                    if(cur.left != null){
                        deque.addFirst(cur.left);
                    }
                }
                flag = true;
            }
            else{//正向
                for(int i = 0; i < len; i++){
                    TreeNode1 cur = deque.removeFirst();
                    temp.add(cur.val);
                    if(cur.left != null){
                        deque.addLast(cur.left);
                    }
                    if(cur.right != null){
                        deque.addLast(cur.right);
                    }
                }
                flag = false;
            }
            res.add(temp);
        }
        return res;
    }
}
/*
[[1], [3, 2], [4, 5, 6, 7]]
 */
